Conseguenza logica
Dati \(\Gamma \subseteq Prop(L)\) e \(\mathrm{Q} \in Prop(L)\), diciamo che \(\mathrm{Q}\) è conseguenza logica di \(\Gamma\), in simboli \[\Gamma \models \mathrm{Q},\] se per ogni interpretazione \(i\), se \(i \models \Gamma\) allora \(i \models \mathrm{Q}\). Scriviamo \(\Gamma \not\models \mathrm{Q}\) per dire che \(\mathrm{Q}\) NON è conseguenza logica di \(\Gamma\).
Quando \(\Gamma = \{ \mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \}\) è un insieme finito, allora scriviamo semplicemente \[\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\] invece di \(\{ \mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \} \models \mathrm{Q}\) e diciamo che \(\mathrm{Q}\) è conseguenza logica delle proposizioni \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\). In particolare, quando \(\Gamma = \{ \mathrm{P} \}\) scriviamo \(\mathrm{P} \models \mathrm{Q}\) e diciamo che \(\mathrm{Q}\) è conseguenza logica di \(\mathrm{P}\).
è immediato verificare che
\(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\) se e solo se \(\models (\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n} ) \rightarrow \mathrm{Q}\).
Teorema
\(\mathrm{P}\) è valida (ovvero una tautologia) se e solo se \(\neg \mathrm{P}\) è insoddisfacibile.
\(\mathrm{P}\) è soddisfacibile se e solo se \(\neg \mathrm{P}\) non è valido,
\(\Gamma \models \mathrm{Q}\) se e solo se \(\Gamma \cup \{ \neg \mathrm{Q} \}\) è insoddisfacibile.
Dimostrazione.
1 e 2 sono ovvie.
Dimostriamo che vale anche 3. Assumiamo che \(\Gamma \models \mathrm{Q}\), e supponiamo per assurdo che \(\Gamma \cup \{ \neg \mathrm{Q} \}\) sia soddisfacibile, ovvero che esista un’interpretazione \(i\) tale che \(i \models \Gamma \cup \{ \neg \mathrm{Q} \}\). Allora si avrebbe che, in particolare, \(i \models \neg\mathrm{Q}\) e \(i \models \mathrm{Q}\) (poichè \(i \models \Gamma\) e \(\Gamma \models \mathrm{Q}\)), contraddizione.
\(\mathrm{P}\) è valida (ovvero una tautologia) se e solo se \(\neg \mathrm{P}\) è insoddisfacibile.
\(\mathrm{P}\) è soddisfacibile se e solo se \(\neg \mathrm{P}\) non è valido,
\(\Gamma \models \mathrm{Q}\) se e solo se \(\Gamma \cup \{ \neg \mathrm{Q} \}\) è insoddisfacibile.
Dimostrazione (continuazione) Assumiamo ora che \(\Gamma \cup \{ \neg \mathrm{Q} \}\) sia insoddisfacibile, e consideriamo una generica interpretazione \(i\) tale che \(i \models \Gamma\): vogliamo mostrare che allora si deve avere anche \(i \models \mathrm{Q}\), cosicchè \(\Gamma \models \mathrm{Q}\) per la genericità di \(i\). Poichè \(i \not\models \Gamma \cup \{ \neg \mathrm{Q} \}\) e \(i \models \Gamma\), allora \(i \not \models \neg \mathrm{Q}\). Quindi \(i \models \mathrm{Q}\), come volevamo.
Se \(\Gamma = \{ \mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \}\) è un insieme finito, si puòì anche osservare direttamente che
| \[\Gamma \models \mathrm{Q}\] | se e solo se | \[(\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}) \to \mathrm{Q} \text{ è valida}\] |
|---|---|---|
| \[\] | se e solo se | \[\neg[(\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n}) \to \mathrm{Q }] \text{ è insoddisfacibile}\] |
| \[\] | se e solo se | \[\mathrm{P}_{1} \wedge \dotsc \wedge \mathrm{P}_{n} \wedge \neg \mathrm{Q} \text{ è insoddisfacibile}\] |
| \[\] | se e solo se | \[\Gamma \cup \{ \neg \mathrm{Q} \} \text{ è insoddisfacibile.}\] |
Date \(\mathrm{P}, \mathrm{Q} \in Prop(L)\) si dice che \(\mathrm{P}\) e \(\mathrm{Q}\) sono logicamente equivalenti, e si scrive \[\mathrm{P} \equiv \mathrm{Q},\] se per ogni interpretazione \(i\) si ha \(i \models \mathrm{P}\) se e solo se \(i \models \mathrm{Q}\). Scriviamo \(\mathrm{P} \not\equiv \mathrm{Q}\) per dire che \(\mathrm{P}\) e \(\mathrm{Q}\) NON sono logicamente equivalenti.
Si noti che
| \[\mathrm{P} \equiv \mathrm{Q}\] | se e solo se | \[\models \mathrm{P} \leftrightarrow \mathrm{Q}\] |
|---|---|---|
| \[\mathrm{P} \equiv \mathrm{Q}\] | se e solo se | \[\mathrm{P} \models \mathrm{Q} \text{e} \mathrm{Q} \models \mathrm{P}\] |
| \[\mathrm{P} \equiv \mathrm{Q}\] | se e solo se | \[i^*(\mathrm{P}) = i^*(\mathrm{Q}) \text{ per ogni interpretazione} i\] |
Osservazione
Per quanto visto, è possibile verificare se
\(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\) oppure \(\mathrm{P} \equiv \mathrm{Q}\)
utilizzando le tavole di verità.
Tuttavia bisogna impostare un’unica tavola di verità in cui valutare simultaneamente tutte le proposizioni coinvolte, e non solo calcolare le tavole di verità delle singole proposizioni una alla volta.
Questo perchè per stabilire se valgano o meno le relazioni di conseguenza logica ed equivalenza logica bisogna considerare le interpretazioni definite su tutte le lettere proposizionali che compaiono in almeno una delle formule \(\mathrm{P}_{1}, \dotsc , \mathrm{P}_{n}\), \(\mathrm{Q}\) oppure \(\mathrm{P}\), \(\mathrm{Q}\), rispettivamente.
Per verificare se \[\mathrm{A} \vee (\mathrm{B} \to \mathrm{C} ) \models \mathrm{A} \wedge \mathrm{B}\] bisogna impostare la seguente tavola di verità:
| \[\mathrm{A}\] | \[\mathrm{B}\] | \[\mathrm{C}\] | \[\mathrm{B} \to \mathrm{C}\] | \[\mathrm{A} \vee (\mathrm{B} \to \mathrm{C} )\] | \[\mathrm{A} \wedge \mathrm{B}\] |
|---|---|---|---|---|---|
| \[0\] | \[0\] | \[0\] | \[1\] | \[1\] | \[0\] |
| \[0\] | \[0\] | \[1\] | \[1\] | \[1\] | \[0\] |
| \[0\] | \[1\] | \[0\] | \[0\] | \[0\] | \[0\] |
| \[0\] | \[1\] | \[1\] | \[1\] | \[1\] | \[0\] |
| \[1\] | \[0\] | \[0\] | \[1\] | \[1\] | \[0\] |
| \[1\] | \[0\] | \[1\] | \[1\] | \[1\] | \[0\] |
| \[1\] | \[1\] | \[0\] | \[0\] | \[1\] | \[1\] |
| \[1\] | \[1\] | \[1\] | \[1\] | \[1\] | \[1\] |
Ricapitolando...
La logica proposizionale ci permette un’analisi logica del ragionamento (matematico) procedendo come segue.
Si introduce un linguaggio “artificiale” \(L\) i cui elementi (le lettere proposizionali \(\mathrm{A}\), \(\mathrm{B}\), …) rappresentano le proposizioni atomiche, ovvero quelle non ulteriormente analizzabili mediante l’uso dei connettivi.
Si considerano i connettivi, particolari costanti logiche che permettono di “collegare” una o più proposizioni per formarne di nuove.
Si introduce il concetto sintattico di formula proposizionale (o proposizione): si introducono regole algoritmiche per costruire e analizzare stringhe di simboli “ben formate”, ovvero tali da poter essere dotate di significato e a cui si puòì di conseguenza assegnare un valore di verità a partire dall’interpretazione dei suoi elementi costitutivi (ovvero a partire dall’interpretazione delle lettere proposizionali che vi occorrono).
Ricapitolando...
Si introduce il concetto semantico di modello, ovvero di una situazione o realtà (astratta) in cui interpretare le formule proposizionali per vedere se, in tale contesto, siano vere o false. In logica proposizionale, questo è realizzato mediante la nozione di interpretazione, ovvero di un assegnamento \(i\) di valori di verità a tutte le lettere proposizionali nel linguaggio \(L\).
A partire dall’interpretazione \(i\), si definiscono le regole che permettono di calcolare il valore di verità di ogni formula proposizionale nel modello dato (valutazione \(v = i^*\) e relazione di soddisfazione \(\models\)).
Considerando insieme vari modelli possibili (ovvero varie interpretazioni), si definiscono i concetti di tautologia, contraddizione, soddisfacibilità, conseguenza logica e equivalenza logica. In particolare, la conseguenza logica \(P \models Q\) dà una formulazione matematicamente precisa della nozione intuitiva di “deduzione corretta”: \(P \models Q\) significa che dall’ipotesi che \(P\) sia vera possiamo concludere che anche la tesi \(Q\) deve essere vera.
Ricapitolando... In questo modo si possono analizzare ragionamenti apparentemente complessi ed evitare errori “logici”.
A prima vista, il seguento ragionamento sembrerebbe corretto:
Se io ho ragione tu hai torto, e se tu hai ragione io ho torto: quindi almeno uno di noi due ha ragione.
Consideriamo il linguaggio \(L = \{ \mathrm{A}, \mathrm{B} \}\) dove
\(\mathrm{A} =\) “io ho ragione” \(\mathrm{B} =\) “tu hai ragione”
(“avere torto” = “non avere ragione”)
Otteniamo la formula proposizionale \((\mathrm{A} \to \neg \mathrm{B}) \wedge (\mathrm{B} \to \neg \mathrm{A} ) \to \mathrm{A} \vee \mathrm{B}\).
è sempre vera (= una tautologia)? No, l’interpretazione \(i (\mathrm{A}) = i(\mathrm{B}) = 0\) (“entrambi abbiamo torto”) descrive una situazione in cui la proposizione, ovvero il ragionamento dato, non è corretto.